package reg_alloc;

import java.io.PrintStream;
import java.util.HashSet;
import java.util.Hashtable;
import flow_graph.FlowGraph;
import java.util.Iterator;
import graph.Node;
import temp.Temp;
import util.List;

public class Liveness extends InterferenceGraph
{
    private FlowGraph graph;
    
    public void addEdge(Node src, Node dst)
    {
        if ( src != dst && !dst.comesFrom(src) && !src.comesFrom(dst))
            super.addEdge(src, dst);
    }
    
    // estruturas usadas para computar a DFA
    private Hashtable<Node, HashSet<Temp>> in;
    private Hashtable<Node, HashSet<Temp>> out;
    private Hashtable<Node, HashSet<Temp>> gen;
    private Hashtable<Node, HashSet<Temp>> kill;
        
    public void show(PrintStream o)
    {       
        for ( List<Node> aux = this.nodes(); aux != null; aux = aux.tail )
        {
            Temp t = revMap.get(aux.head);
            
            o.print(t + ": [ ");
            for ( List<Node> adjs = aux.head.adj(); adjs != null; adjs = adjs.tail )
                o.print( revMap.get(adjs.head) + " ");
            o.println("]");
        }
    }
    
    // coisas uteis
    private MoveList moveList = null;
    
    private Hashtable<Node, Temp> revMap = new Hashtable<Node, Temp>();
    private Hashtable<Temp, Node> map = new Hashtable<Temp, Node>();
    
    public Liveness(FlowGraph g)
    {
        super();
    
        graph = g;
            
        computeGenKill();
        computeDFA();
        buildInterference();
    }

    public void dump(PrintStream outStream)
    {
        int c=0;
        for(List<Node> aux = graph.nodes(); aux != null; aux = aux.tail, c++)
        {
            HashSet<Temp> i = in.get(aux.head);
            HashSet<Temp> o = out.get(aux.head);
            HashSet<Temp> g = gen.get(aux.head);
            HashSet<Temp> k = kill.get(aux.head);
            
            outStream.println(c+": gen:"+g+" kill:"+k+" in:"+i+" out:"+o);
        }
    }
    
    private void computeGenKill()
    {
        kill = new Hashtable<Node, HashSet<Temp>>();
        gen  = new Hashtable<Node, HashSet<Temp>>();
        
        for(List<Node> nodes = graph.nodes(); nodes != null; nodes = nodes.tail)
        {
            HashSet<Temp> k = new HashSet<Temp>();
            HashSet<Temp> g = new HashSet<Temp>();
            
            // kill
            for ( List<Temp> aux = graph.def(nodes.head); aux != null; aux = aux.tail )
                k.add(aux.head);
            
            // gen
            for ( List<Temp> aux = graph.use(nodes.head); aux != null; aux = aux.tail )
                g.add(aux.head);
            
            kill.put(nodes.head, k);
            gen.put(nodes.head, g);
        }
    }
    
    /*
     * Foi adotado o algoritmo Liveness iterativo. Suas equacoes sao:
     *  in[n] = use[n] _UNIAO_ (out[n] - kill[n])
     * 	out[n] = _UNIAO_ {s pertencente a succ[n]} in[s]
     * 
     * O que e' equivalente a:
	 * for each n
	 *     in[n] {}; out[n] {}
	 * repeat
	 *    for each n
	 *       in[n]  in[n]; out[n] out[n]
	 *       in[n]  use[n] (out[n] def[n])
	 *       out[n] succ[n]in[s]
	 * until in[n] = in[n] and out[n] = out[n] for all n
	 * 
     */
    private void computeDFA()
    {    	   	
    	in  = new Hashtable<Node, HashSet<Temp>>();
        out = new Hashtable<Node, HashSet<Temp>>();
     
        // Auxiliares para condicao de parada : in′[n] e out′[n]
    	Hashtable<Node, HashSet<Temp>> in_anterior  = new Hashtable<Node, HashSet<Temp>>();
    	Hashtable<Node, HashSet<Temp>> out_anterior = new Hashtable<Node, HashSet<Temp>>();

    	/*
    	 * Inicializando in[] e out[]:
    	 * for each n : in[n] {}; out[n] {};
    	 */
    	for (List<Node> nodes = graph.nodes(); nodes != null; nodes = nodes.tail) {
    		in.put(nodes.head, new HashSet<Temp>());
    		out.put(nodes.head, new HashSet<Temp>());
    		in_anterior.put(nodes.head, new HashSet<Temp>());
    		out_anterior.put(nodes.head, new HashSet<Temp>());
    	}
    	
        do
        {
	        /*
	         * Para todo no' pertencente ao grafo de controle de fluxo
	         * for each n
	         */
        	for(List<Node> nos = graph.nodes(); nos != null; nos = nos.tail)
	        {
	        	// Declaracao de variaveis
	        	HashSet<Temp> no_in     = new HashSet<Temp>();	
	        	HashSet<Temp> no_out    = new HashSet<Temp>();
	        	HashSet<Temp> in_temp   = new HashSet<Temp>();
	        	HashSet<Temp> out_temp  = new HashSet<Temp>();
	        	Iterator<Temp> iterator = null;
	        	List<Node> s = null;
	        	
	        	/*
	        	 * Atualizando in'[n] out'[n]:
	        	 * in'[n] = in[n]; out'[n] = out[n]
	        	 */
	        	in_anterior.remove(nos.head);
	        	in_anterior.put(nos.head, (HashSet<Temp>)in.get(nos.head).clone() );
	        	out_anterior.remove(nos.head);
	        	out_anterior.put(nos.head, (HashSet<Temp>)out.get(nos.head).clone() );
	        	
	        	/*
	        	 * Calculo in[n]:
	        	 * in[n]  = use[n] UNIAO (out[n] - kill[n])
	        	 */
	        	// Parte 1 : in[n] = use[n]
	        	no_in.addAll(gen.get(nos.head));
	        	
	        	// Parte 2 : in[n] =+ ( out[n] - kill[n] )
	        	out_temp = out.get(nos.head);	       	
	        	// Se existir algum no' em out[n]
	        	if (out_temp != null) {
	        		iterator = out_temp.iterator();
		        		
	        		// Enquanto existir algum no' no conjunto out[n]
	        		while(iterator.hasNext())
		        	{
		        		Temp temp_aux = iterator.next();
		        		// Somente os nos que nao pertencem a kill[n] sao adicionados a in[n]
		        		if (kill.get(nos.head).contains(temp_aux) == false)
		        			no_in.add(temp_aux);
		        	}
	        	}
	        	
	        	// Termino calculo in : Atualiza in[n]
	        	in.remove(nos.head);
	        	in.put(nos.head, (HashSet<Temp>)no_in.clone());
	        	
     	
	        	/*
	        	 * Calculo out[n]:
	        	 * out[n] = UNIAO {s pertencente a succ[n]} in[s]
	        	 */
	        	for (s = nos.head.succ() ; s != null ; s = s.tail )
	        	{
	        		// Adiciona o in do sucessor no out do no
	        		in_temp = in.get(s.head);
	        		if (in_temp != null)
	        			no_out.addAll(in_temp);	        		
	        	}	        	
	        	
	        	// Termino calculo out : Atualiza out[n]	
	        	out.remove(nos.head);
	        	out.put(nos.head, (HashSet<Temp>)no_out.clone());
	        	
	        }

        /*
         * Verifica se houve mudanca nos conjuntos in[] e out[]
         * in'[n] = in[n] & out'[n] = out[n]   
         */
        } while ( (!in_anterior.equals(in)) || (!out_anterior.equals(out)) );
    	
    }
    
    private Node getNode(Temp t)
    {
        Node n = map.get(t);
        
        if ( n == null )
        {
            n = this.newNode();
            
            map.put(t, n);
            revMap.put(n, t);
        }
        
        return n;
    }
    
    private void handle(Node instr)
    {
        for( List<Temp> defs = graph.def(instr); defs != null; defs = defs.tail )
        {
            Node currentTemp = this.getNode(defs.head);
            
            for( Temp liveOut : out.get(instr) )
            {                
                Node currentLiveOut = this.getNode(liveOut);
                this.addEdge(currentTemp, currentLiveOut);
            }
        }
    }
    
    private void handleMove(Node instr)
    {
        Node dst = this.getNode(graph.def(instr).head);
        Node src = this.getNode(graph.use(instr).head);
        
        moveList = new MoveList(src, dst, moveList);
        
        for( Temp t : out.get(instr) )
        {
            Node currentOut = this.getNode(t);
            
            if ( currentOut != src )
            {
                //this.addEdge(currentOut, dst);
                this.addEdge(dst, currentOut);
            }
        }
    }
    
    private void buildInterference()
    {
        // Estamos sentados sobre ombros de um gigante...
        // Aqui, nos temos uma lista sobre todos os temporarios
        // vivos no fim de cada no. Desta forma, eh relativamente
        // facil construir a lista de adjacencia.
        
        for ( List<Node> instrs = graph.nodes(); instrs != null; instrs = instrs.tail )
        {
            Node current = instrs.head;
            
            if ( graph.isMove(current))
                handleMove(current);
            else
                handle(current);
        }
    }
    
    public Node tnode(Temp temp)
    {
        Node n = map.get(temp);
        
        if ( n == null )
        {
            map.put(temp, n = newNode() );
            revMap.put(n, temp);
        }
        
        return n;
    }

    public Temp gtemp(Node node)
    {
        return revMap.get(node);
    }

    public MoveList moves()
    {
        return moveList;
    }

    public HashSet<Temp> Out(Node node)
    {
        return out.get(node);
    }    
}
